#ifndef _ALLOCATOR_HPP_
#define _ALLOCATOR_HPP_
#define FREE_VALUE          213
#define READPROOF_LOW       46
#define READPROOF_HIGH      77
#define COOKIE_SIZE         4
#define READPROOF_SIZE      2
#define MAX_SIZE            4096
/*
  Cookie使用来记录某块内存的。
  不推荐较小的数据结构使用Allocator。因为这样会损耗很多空间在Cookie上。

  如何判断一个区域是不是free状态：
  
      首先确认是否有连续3个或3个以上的FREE_VALUE
      如果有，则向前寻找READPROOF,
      找到后，得到READPROOF前面的数字，即该Cookie代表的已占大小。
      如果该Cookie表明那几个连续的FREE_VALUE是在自己范围之外，则说明这几个FREE_VALUE是相当靠谱的，可以使用。

      当然，这个算法仍然有一定风险。
      比如说正好找到一个本质上不是READPROOF的值和READPROOF一致的2个连续区域，且其中的数值表明FREE_VALUE是在自己范围之外，但实际上并非如此。
      不过这种可能性微乎其微。
*/
class Allocator
{
public:
  Allocator():border(0)
  {
    for(int i=0,len=MAX_SIZE;i<len;i++){
      space[i]=FREE_VALUE;
    }
  }

  template <typename T>
  T* alloc()
  {
    if(sizeof(T)+border+COOKIE_SIZE>MAX_SIZE){                 
      return search<T>();
    }  
    else{
      type::u16* size_ptr=(type::u16*)&space[border];                          
      *size_ptr=sizeof(T);
      space[border+2]=READPROOF_LOW;
      space[border+3]=READPROOF_HIGH;
      T* ptr=(T*)&space[border+COOKIE_SIZE];                      
      border+=(sizeof(T)+COOKIE_SIZE);
      return ptr;
    }  
  }
  
  template <typename T>
  void dealloc(T* ptr)
  {
    type::u8* tmp=(type::u8*)ptr;                          
    type::u16* sizevalue_ptr=(type::u16*)(tmp-COOKIE_SIZE);
    tmp=(type::u8*)sizevalue_ptr;
    for(int i=0,len=*sizevalue_ptr+COOKIE_SIZE;i<len;i++)  { *(tmp++)=FREE_VALUE; } 
  }
  
  type::addr malloc(type::u32 size);
  void free(type::addr);
  void print_state();
  
private:
  template <typename T>
  T* search() // search for free space!
  {
    for(int i=0,len=MAX_SIZE;i<len;i++){
      if(space[i]==space[i+1]&&space[i]==space[i+2]&&space[i]==FREE_VALUE){
        if(space[i+3]==READPROOF_LOW && space[i+4]==READPROOF_HIGH) continue;  
        if(find_free_size(i)<(int)(sizeof(T)+COOKIE_SIZE)) continue;
        if(check_readproof(i)==true){                  
          return research<T>(i);
        }
      }
    }
    return (T*)0;
  }
  
  template <typename T>
  T* research(int i){   
    type::u16* size_ptr=(type::u16*)&space[i];                          
    *size_ptr=sizeof(T);
    space[i+2]=READPROOF_LOW;
    space[i+3]=READPROOF_HIGH;
    T* ptr=(T*)&space[i+COOKIE_SIZE];                      
    return ptr;
  }  
  
  int find_free_size(int index); //返回连续有多少个FREE_VALUE
  bool check_readproof(int index); //返回true,如果我们的FREE_VALUE不在范围内。
  int                border;
  type::u8           space[MAX_SIZE];         // space for dynamic memory management
};   

#endif
